package demo.practice.uf;

public class P684 {


    public static void main(String[] args) {
        P684 p684= new P684();
        p684.findRedundantConnection(new int[][]{{1,2},{1,3},{2,3}});
    }

    public int[] findRedundantConnection(int[][] edges) {
        if(edges==null|| edges.length==0)
            return new int[0] ;

        UFRankUnion uf = new UFRankUnion(edges.length);

        int [] res= new int[2];
        for (int[] edge : edges) {
            int a= edge[0];
            int b= edge[1];

            if(uf.findP(a-1)==uf.findP(b-1))
                res= new int[]{a,b};    //说明a和b 以前就链接上了，所以现在能围成环
            else{
                uf.join(a-1,b-1);
            }
        }
        return res;
    }
}
